package com.bascker.algorithm.practice.dp;

import java.util.Objects;

/**
 * 不同路径 II:
 * 一个机器人位于一个 m x n 网格的左上角, 机器人每次只能向下或者向右移动一步。
 * 机器人试图达到网格的右下角, 现在考虑网格中有障碍物。那么从左上角到右下角将会有多
 * 少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。
 * <p>
 * note: m, n 均不超过 100
 * <p>
 * in: [
 * [0,0,0],
 * [0,1,0],
 * [0,0,0]
 * ]
 * <p>
 * out: 2
 * 解釋:
 * 3x3 网格的正中间有一个障碍物.左上角到右下角一共有 2 条不同的路径：
 * 1. 向右 -> 向右 -> 向下 -> 向下
 * 2. 向下 -> 向下 -> 向右 -> 向右
 *
 * @apiNote leetcode T63
 */
public class UniquePathII {

    /**
     * dp(i, j) 表示从坐标(i,j)到终点，有几条路径， 状态转移方程如下
     * dp(i - 1, j) + dp(i, j - 1)     # (i, j) 上无障碍物
     * dp(i, j) =   0,                              # (i, j) 上有障碍物
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (Objects.isNull(obstacleGrid) || obstacleGrid.length == 0) {
            return 0;
        }

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if (obstacleGrid[m - 1][n - 1] == 1) {
            return 0;
        }

        int[][] dp = new int[m][n];
        // 初始化第1行: 只从上边界的格子走过去(有障碍，则路径数为0，否则为1)
        // 必须把 obstacleGrid[i][j] == 0 的条件放在 for(;condition;;)处,
        // 只要其中有一个点存在障碍物，后面的都是 0
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        // 初始化第1列: 只从左边界的格子走过去
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 有障碍物
                if (obstacleGrid[i][j] == 1) {
                    continue;
                }

                // 无障碍物
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }


}
